import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] meetings = {{1,4,3},{0,4,3}};
        System.out.println(s.findAllPeople(5, meetings, 3));
    }

    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        /**
         * 找出知晓秘密的所有专家-并查集解法*/
        // 1 预处理
        // -按照会议时间对数据进行排序
        Arrays.sort(meetings, (a, b) -> a[2]-b[2]);
        // -初始化并查集
        initialize(n);
        // -初始化知情标签
        union(firstPerson, 0);
        know[find(0)] = true;
        // -创建记录时间遍历
        int curTime = 0;

        // 2 遍历
        // -该结构用于存储每一时间段会议人数，便于后续解散不知情集合
        int[] temporaryArray = new int[2_00000];
        int i = 0;
        for(int[] e: meetings) {
            // 2.1 时间变动，解散上次会议所有不知情集合
            if(e[2] != curTime) {
                // -解散
                while(i > 0) {
                    int t = temporaryArray[--i];
                    if(!know[find(t)]) {
                        father[t] = t;
                    }
                }
                // -重置时间
                curTime = e[2];
            }
            // 2.2 合并同组会议专家
            union(e[0], e[1]);

            temporaryArray[i++] = e[0];
            temporaryArray[i++] = e[1];
        }

        // 3 返回值
        List<Integer> retArray = new LinkedList<>();
        for(int k = 0; k < n; k++) {
            if(know[find(k)]) {
                retArray.add(k);
            }
        }
        return retArray;
    }

    // 实现并查集
    public static int MAX_N;
    public static int[] father;
    public static int[] stack;
    public static int[] size;
    public static boolean[] know;

    public static void initialize(int n) {
        /**
         * 初始化处理*/
        MAX_N = n;
        father = new int[MAX_N];
        stack = new int[MAX_N];
        size = new int[MAX_N];
        know = new boolean[MAX_N];
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 查找a元素所在集合的代表元素，并作扁平化优化*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合，并作小挂大优化*/
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                father[fb] = fa;
                know[fa] = know[fb] || know[fa];
            } else {
                size[fb] += size[fa];
                father[fa] = fb;
                know[fb] = know[fb] || know[fa];
            }
        }
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否处于同一集合中*/
        return find(a) == find(b);
    }
}
